package trim.common.bp;

import trim.common.Format;
import trim.common.inputdata.FormatOrder;
import trim.common.Material;
import trim.common.inputdata.InputData;
import trim.common.result.Pattern;
import trim.common.result.PatternItem;
import trim.common.result.TrimResult;

/**
 * BestPartition.java
 * Класс реализующий метод ветвей и границ для задачи форматного раскроя.
 * В основу положен алгоритм описанный в книге И.В.Романовского
 * "Алгоритмы решения экстремаьных задач"
 *
 * Created on 18.11.2008 20:41:02
 * @author Дмитрий
 */
public class BestPartition
{
  protected int sim,  minm,  tailm;
  //int sim,minm,tailm;
  protected int BPRes[],  BPTmpRes[];//решение и временное решение BP
  protected int formatCount=0;//количество оставшихся рулонов
  protected InputData inputData;
  protected int mint;
  protected int maxt;
  protected int S;
  protected int[] C;
  protected int n;
  protected int[] L;
  protected int KnifeCount;

  public BestPartition(InputData inputData) throws BPException
  {
    this.inputData=inputData;
    n=inputData.getFormatOrderList().size();
    if(inputData.getMaterialStockList().size()==0)
      throw new BPException("Empty materialCountList");
    Material m=inputData.getMaterialStockList().get(0).getMaterial();
    S=m.getLength()-m.getMinEdge()*2;
    mint=2*(m.getMaxEdge()-m.getMinEdge());
    maxt=m.getKnifeInterval();
    KnifeCount=m.getKnifeCount();
    C=new int[n];
    L=new int[n];
    int i=0;
    for (FormatOrder fc : inputData.getFormatOrderList())
    {
      L[i]=fc.getCount();
      C[i++]=fc.getFormat().getLength();
    }
  }

  public TrimResult solve(int leftTambour)
  {
    minm=0;
    sim=0;
    tailm=0;
    for (int i=0; i<n; minm+=L[i++])
      sim+=L[i]*C[i];
    formatCount=minm;
    BPRes=new int[formatCount];
    BPTmpRes=new int[formatCount];
    if (leftTambour>0)
    {
      minm=sim%S;
      int t=minm>0?1:0;
      if (leftTambour>sim/S+t)
        minm=leftTambour;
      else
        minm=sim/S+t;
      tailm=minm*S-sim+S;
      sim=minm;
    } else
    {
      tailm=minm*S-sim+S;
      if (sim%S==0)
        sim--;
      sim=sim/S+1;
    }
    minm++;
    if (formatCount>0)
      BPRes[0]=-100000;
    while (formatCount>0&&BPRes[0]==-100000)
    {
      bestPartition(0, formatCount, 0, 0, S, KnifeCount-1);
      minm++;
      tailm+=S;
    }

    return makeTrimResult();
  }

  /**
   * Преобразование результата перебора в {@link TrimResult}
   * @return {@link TrimResult}
   */
  protected TrimResult makeTrimResult()
  {
    TrimResult tr=new TrimResult();
    Pattern p=null;
    for (int i=0; i<formatCount; i++)
    {
      int x=BPRes[i];
      if (x<0)
      {
        p=new Pattern();
        p.setMaterial(inputData.getMaterialStockList().get(0).getMaterial());
        p.setCount(1);
        x=-x;
        tr.add(p);
      }
      p.add(new PatternItem(new Format(x)));
    }
    return tr;
  }

  /**
   * @param m использованное число тамбуров
   * @param ml число не уложенных заготовок
   * @param p координата последнего элемента в массиве результата
   * @param q последний уложенный на текущий тамбур формат
   * @param tail остаток на текущем тамбуре
   * @param kc количество свободных ножей на текущем тамбуре
   */
  protected void bestPartition(int m, int ml, int p, int q, int tail, int kc)
  {
    int i, j=0;
    int k, t, r;

    if (tailm<0/*(m>minm)*/||((minm<=sim))
          //((ml>0)&&(tail<C[n-1])&&(tailm<tail))
          )
      return;
    if (ml==0)
    {
      if (m<minm&&((tail<=mint)||(tail>=maxt)))
      {
        for (i=0; i<formatCount; i++)
        {
          BPRes[i]=BPTmpRes[i];
        }
        tailm=tailm-S*(minm-m);
        minm=m;
      }
    } else
    {
      if (tail!=S&&tail>=C[n-1]&&kc>0)
      {
        //for(i=n-1;i>=q;i--) - для перебора вариантов с конца
        for (i=q+1; i<n; i++)
        {
          if ((L[i]>0)&&(C[i]<=tail))
          {
            k=tail/C[i];
            if (k>Math.min(L[i], kc))
              k=Math.min(L[i], kc);
            for (r=0; r<k; r++)
            {
              BPTmpRes[p]=C[i];
              p++;
              L[i]--;
              kc--;
            }
            p--;
            tail-=C[i]*(k-1);
            ml-=(k-1);
            if(i==n-1)
            {
              bestPartition(m, ml-1, p+1, i, tail-C[i], kc);
              p-=k;
              kc+=k;
              tail+=k*C[i];
              ml+=k;
              L[i]+=k;
              //minC=n-1;
            }else
            for (r=0; r<k; r++)
            {

              bestPartition(m, ml-1, p+1, i, tail-C[i], kc);
              p--;
              kc++;
              tail+=C[i];
              ml++;
              L[i]++;
            }
            p++;
            tail-=C[i];
            ml--;

            j++;
          }
        }
      }
      tailm=tailm-tail;
      if ((j==0)&&(tailm>=0)&&(minm-m-1)*(KnifeCount-1)>=ml//&&((tail==S)||(tail<=S))
            &&((tail<=mint)||(tail>=maxt)))
      {
        //for(i=0;i<n;i++)
        i=0;
        while (L[i]==0)
          i++;
        if (L[i]>0)
        {
          BPTmpRes[p]=-C[i];
          t=S;
          k=t/C[i];
          p++;
          kc=KnifeCount-1;
          if (k>Math.min(L[i], kc))
            k=Math.min(L[i], kc);
          L[i]--;
          kc--;
          for (r=0; r<k-1; r++)
          {
            BPTmpRes[p]=C[i];
            p++;
            L[i]--;
            kc--;
          }
          p--;
          t-=C[i]*(k-1);
          ml-=(k-1);

          for (r=0; r<k; r++)
          {
            bestPartition(m+1, ml-1, p+1, i, t-C[i], kc);
            p--;
            kc++;
            t+=C[i];
            ml++;
            L[i]++;
          }
          p++;
          //L[i]++;kc++;
          t-=C[i];
          ml--;
        }
      }
      tailm=tailm+tail;
    }
  //return new BPResult(bpData.BPRes);
  }
}
